首先有个想法，如果该位为 且不是前导 ，则将 的数量加一，最后看 是否出现了至少 次。
但这样有个问题，比如在 时， 就不会被计入答案 ，原因是 的前导 也算在了它二进制的位数中。
所以还要记录前导零的数量 ，最后判断是否出现至少 即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 35;
int a[ MAXN + 5 ] , len , dp[ MAXN + 5 ][ MAXN + 5 ][ MAXN + 5 ];
int dfs( int pos , int lead , int leadnum , int limit , int sum ) {
if( pos == len + 1 ) return sum >= len - leadnum - sum;
if( ~dp[ pos ][ sum ][ leadnum ] && !lead && !limit ) return dp[ pos ][ sum ][ leadnum ];
int Ans = 0 , Mbit = limit ? a[ len - pos + 1 ] : 1;
for( int i = 0 ; i <= Mbit ; i ++ ) {
if( lead && i == 0 ) Ans += dfs( pos + 1 , 1 , leadnum + 1 , limit & ( i == Mbit ) , sum );
else Ans += dfs( pos + 1 , 0 , leadnum , limit & ( i == Mbit ) , sum + ( i == 0 ) );
}
if( !lead && !limit ) dp[ pos ][ sum ][ leadnum ] = Ans;
return Ans;
}
int Solve( int x ) {
len = 0; for( ; x ; x /= 2 ) a[ ++ len ] = x % 2;
memset( dp , -1 , sizeof( dp ) );
return dfs( 1 , 1 , 0 , 1 , 0 );
}
int l , r;
int main( ) {
scanf("%d %d",&l,&r);
printf("%d\n", Solve( r ) - Solve( l - 1 ) );
return 0;
}
